public class ShellSort {
    public static void main(String[] args) {
//        int[] arr = {6,5,7,3,9,8,5,2};
        int[] arr = {1,2,1,2,1,3};
        shellSort(arr);
        for (int n : arr) {
            System.out.println(n);
        }
    }

    private static void shellSort(int[] arr) {
        int gap = arr.length/2;
        while (gap > 0) {
            for (int i = 0; i < gap; i++) {
                int index = i+gap;
                while (index < arr.length) {
                    int temp = arr[index];
                    int j = index-gap;
                    while (j >= 0 && arr[j] > temp) {
                        arr[j+gap] = arr[j];
                        j -= gap;
                    }
                    arr[j+gap] = temp;
                    index += gap;
                }
            }
            gap = gap/2;
        }
    }
}
